package stackAndQueue;

import java.util.*;

public class StackSolution01 {
    //232. 用栈实现队列
    //请你仅使用两个栈实现先入先出队列。
    //队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
    //将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。
    //每次 pop 或 peek 时，
    // 若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，
    // 这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
    class MyQueue {
        private Stack<Integer> stackIn; //输入栈
        private Stack<Integer> stackOut; //输出栈

        public MyQueue() {
            stackIn = new Stack<>();
            stackOut = new Stack<>();
        }

        public void push(int x) {
            stackIn.push(x);
        }

        public int pop() {
            if(stackOut.isEmpty()) {
                inToOut();
            }
            return stackOut.pop();

        }

        public int peek() {
            if(stackOut.isEmpty()) {
                inToOut();
            }
            return stackOut.peek();

        }

        public boolean empty() {
            return stackIn.isEmpty() && stackOut.isEmpty();

        }
        private void inToOut() {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
    }

    /**
     * 225. 用队列实现栈 -easy
     * 请你仅使用两个队列实现一个后入先出（LIFO）的栈，
     * 并支持普通栈的全部四种操作（push、top、pop 和 empty）。
     *用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。
     *
     * 但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！
     */
    class MyStack {
        private Queue<Integer> queue1; // 和栈中保持一样元素的队列
        private Queue<Integer> queue2; // 辅助队列
        public MyStack() {
            queue1 = new LinkedList<>();
            queue2 = new LinkedList<>();
        }

        public void push(int x) {
            queue2.offer(x); // 先放在辅助队列中
            while (!queue1.isEmpty()){
                queue2.offer(queue1.poll());
            }
            Queue<Integer> queueTemp;
            queueTemp = queue1;
            queue1 = queue2;
            queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中
        }

        public int pop() {
            return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可
        }

        public int top() {
            return queue1.peek();

        }

        public boolean empty() {
            return queue1.isEmpty();

        }
    }

    //优化 -用一个队列来模拟栈
    class MyStackOnlyOneQueue {
        private Queue<Integer> queue;
        public MyStackOnlyOneQueue() {
            queue = new LinkedList<>();
        }
        public void push(int x) {
            queue.offer(x);
        }
        public int pop() {
            int size = queue.size();
            while (size > 1) {
                queue.add(queue.poll());
                size--;
            }
            return queue.poll();
        }
        public int top() {
            int size = queue.size();
            while (size > 1) {
                queue.add(queue.poll());
                size--;
            }
            int res = queue.poll();
            queue.add(res);
            return res;
        }
        public boolean empty() {
            return queue.isEmpty();
        }

    }

    /**
     * 20. 有效的括号 -easy
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * @param s
     * @return
     */

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char ch : s.toCharArray()) {
            if(ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {
                //有右括号但是栈空 --说明这个右括号没有对应的左括号
                if(stack.isEmpty()) {
                    return false;
                }
                char left = stack.pop();
                if(left == '(' && ch != ')') {
                    return false;
                } else if(left == '[' && ch != ']') {
                    return false;
                } else if(left == '{' && ch != '}') {
                    return false;
                }
                //左右括号抵消
            }
        }
        //如果最后栈里还有左括号，则返回false
        if(stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }


    /**
     * 1047. 删除字符串中的所有相邻重复项 -easy
     * @param s
     * @return
     */
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for(char ch : s.toCharArray()) {
            if(stack.isEmpty() || stack.peek() != ch) {
                stack.push(ch);
            } else {
                //栈顶元素与该元素相等-消去
                stack.pop();
            }
        }
        //栈里剩下的就是不重复的元素
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        //记得反一些
        return sb.reverse().toString();
    }

    /**
     * 150. 逆波兰表达式求值 -medium
     * 这题也类似1047题，只是不是消除而是运算后重新入栈
     * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
     *
     * 请你计算该表达式。返回一个表示表达式值的整数。
     * @param tokens
     * @return
     */
/*    逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。
    平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
    该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
    逆波兰表达式主要有以下两个优点：
    去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
    适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。*/
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String token : tokens) {
            if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                if(stack.size() < 2) {
                    return Integer.MIN_VALUE; //表示表达式有问题
                }
                //栈后进先出，别搞反除数和被除数
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            } else {
                //是数字则入栈
                stack.push(Integer.parseInt(token));
            }

        }
        return stack.isEmpty() ? Integer.MIN_VALUE : stack.pop();
    }


    /**
     * 239. 滑动窗口最大值 -hard
     * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
     * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     * 返回 滑动窗口中的最大值
     * @param nums
     * @param k
     * @return
     */
    class MyQueueTedium {
        Deque<Integer> deque = new LinkedList<>();
        //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
        //同时判断队列当前是否为空
        void poll(int val) {
            if (!deque.isEmpty() && val == deque.peek()) {
                deque.poll();
            }
        }
        //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
        //保证队列元素单调递减
        //比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
        void add(int val) {
            while (!deque.isEmpty() && val > deque.getLast()) {
                deque.removeLast();
            }
            deque.add(val);
        }
        //队列队顶元素始终为最大值
        int peek() {
            return deque.peek();
        }
    }
    //这是使用单调队列的经典题目。
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        int len = nums.length - k + 1;
        //存放结果元素的数组
        int[] res = new int[len];
        int num = 0;
        //自定义队列
        MyQueueTedium myQueue = new MyQueueTedium();
        //先将前k的元素放入队列
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        res[num++] = myQueue.peek();
        for (int i = k; i < nums.length; i++) {
            //滑动窗口移除最前面的元素，移除时判断该元素是否放入队列
            //如果最大值可能在滑动窗口左边界的左侧，并且随着窗口向右移动，
            //则将该元素移除 -因为下一个窗口一定没这个值
            myQueue.poll(nums[i - k]);
            //滑动窗口加入最后面的元素
            myQueue.add(nums[i]);
            //记录对应的最大值
            res[num++] = myQueue.peek();
        }
        return res;
    }

    public int[] maxSlidingWindow_01(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int len = nums.length - k + 1;
        int[] res = new int[len];
        for(int i=0;i<k;i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        res[0] = nums[deque.peekFirst()];
        for(int i=k;i<nums.length;i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            //窗口左侧元素全部移除
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            res[i-k+1] = nums[deque.peekFirst()];
        }
        return res;
    }


    /**
     * 347. 前 K 个高频元素 -medium
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //优先队列-大顶堆
        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            priorityQueue.offer(entry);
        }
        int[] res = new int[k];
        for(int i=0;i<k;i++) {
            res[i] = priorityQueue.poll().getKey();
        }
        return res;
    }



    public static void main(String[] args) {
        MyQueue myQueue = new StackSolution01().new MyQueue();
        myQueue.push(1);
        myQueue.push(2);
        myQueue.push(3);
        System.out.println(myQueue.peek());
        myQueue.push(4);
        myQueue.push(5);
        while(!myQueue.empty()) {
            System.out.println(myQueue.pop());
        }

    }

}
